/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.快慢指针;

import java.util.List;

/**
 * Title：NC4-寻找链表闭环
 * Description：
 * @author WZQ
 * @version 1.0.0
 * @date 2021/1/7
 */
public class NC4 {

    /**
     * 思路1：hash map/set
     * 开一个哈希表，标记访问过的节点，
     * 如果重复访问了某一节点，说明有环。
     * 需要额外O(n)的空间复杂度。
     */


    /**
     * 思路2：快慢指针
     * 用一快一慢指针，开始两个指针都指向链表头部。
     * 慢指针每次向前走一步，快指针每次向前走两步。
     * 如果有环，则两个指针最终一定会相遇。
     * 这种方法无须额外的空间。
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode s = head;
        ListNode q = head;
        while (q != null && q.next != null){
            s = s.next;
            q = q.next.next;
            if (s == q){
                return true;
            }
        }
        return false;
    }

    //Definition for singly-linked list.
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
